package 动态规划;

/**
 * @Author: biubiu0002
 * @Date: 2021-09-04 23:11
 **/
public class 最大子段和 {
    public static void main(String[] args) {
        int[] input = {1,-2,4,3,5,-6,9};
//        System.out.println(maxSubSum(input,0,6));
        System.out.println(ziduanhe(input));
    }

    public static int maxSubSum(int[]a ){
        //b[j] = max{b[j-1]+a[j],a[j]}
        int n = a.length;
        int i =0;
        while(a[i]<0&&i<n){
            i++;
        }

        int dp[] = new int[n];
        dp[i]=a[i];
        for(i=i+1;i<n;i++){
            dp[i] = Math.max(dp[i-1]+a[i],a[i]);
        }
        return dp[n-1];
    }

    public static int ziduanhe(int[] nums){
        int n = nums.length;
        int[]dp = new int[n];
        dp[0]=nums[0];
        int max = Integer.MIN_VALUE;
        for(int i=1;i<n;i++){
            if(dp[i-1]>0){
                dp[i]=dp[i-1]+nums[i];
            }
            else if(dp[i-1]<=0){
                dp[i]=nums[i];
            }
            max = Math.max(max,dp[i]);

        }
        return max;


    }

    /**
     * 分治法 时间 O(nlogn)
     * @param a
     * @param left
     * @param right
     * @return
     */
    public static int maxSubSum(int[] a, int left, int right) {
        /**
         * 三种情况
         * 左边
         * 右边
         * 左边最大+右边最大
         */
        // base case
        if (left == right) {
            return a[left] > 0 ? a[left] : 0;
        } else {
            int mid = left + ((right - left) >>> 1);
            int leftSum = maxSubSum(a, left, mid);
            int rightSum = maxSubSum(a, mid + 1, right);
            int midSum=0;
            int sum=0;
            int s1 = 0, lefts = 0;
            for (int i = mid; i >= left; i--){
                lefts+=a[i];
                if(lefts>s1){
                    s1=lefts;
                }
            }
            int s2=0,rights=0;
            for(int i=mid+1;i<=right;i++){
                rights+=a[i];
                if(rights>s2){
                    s2=rights;
                }
            }
            midSum=s1+s2;
            sum=midSum;
            if(sum<leftSum){
                sum=leftSum;
            }
            if(sum<rightSum){
                sum=rightSum;
            }
            return sum;


        }


    }
}
